package com.dycong.common.leetcode;

import com.dycong.common.leetcode.ds.ListNode;

/**
 * @author dycong
 * @date 2019/12/3 8:24
 */
public class ReverseList_206 {

    public static void main(String[] args) {
        ReverseList_206 reverseList_206 = new ReverseList_206();
        ListNode head = ListNode.generate(10);
        System.out.println(ListNode.format(head));
        ListNode reverseHead = reverseList_206.reverseList(head);
        System.out.println(ListNode.format(reverseHead));
        ListNode reverseHead2 = reverseList_206.reverseList_recursion(reverseHead);
        System.out.println(ListNode.format(reverseHead2));
    }

    /**
     * 方法一：迭代
     * 假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
     * <p>
     * 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
     * <p>
     * 迭代方式
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nextNode;
        }
        return pre;
    }

    /**
     *
     *
     * 递归方式
     *
     * @param head
     * @return
     */
    public ListNode reverseList_2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList_2(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    public ListNode reverseList_recursion(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode p = reverseList_recursion(head.next);

        head.next.next = head;
        head.next = null;
        return p;
    }

}
